use std::ptr;
const AVL_TREE_NULL: *mut std::ffi::c_void = ptr::null_mut();
type AVLTreeKey = *mut std::ffi::c_void;
type AVLTreeValue = *mut std::ffi::c_void;
#[repr(C)]
struct AVLTree {
    root_node: *mut AVLTreeNode,
    compare_func: AVLTreeCompareFunc,
    num_nodes: u32,
}
#[repr(C)]
struct AVLTreeNode {
    children: [*mut AVLTreeNode; 2],
    parent: *mut AVLTreeNode,
    key: AVLTreeKey,
    value: AVLTreeValue,
    height: i32,
}
#[derive(Debug, Clone, Copy, PartialEq)]
enum AVLTreeNodeSide {
    AVL_TREE_NODE_LEFT,
    AVL_TREE_NODE_RIGHT,
}
type AVLTreeCompareFunc = extern "C" fn(AVLTreeValue, AVLTreeValue) -> i32;
fn avl_tree_new(compare_func: AVLTreeCompareFunc) -> *mut AVLTree {
    unsafe {
        let new_tree = malloc(mem::size_of::<AVLTree>()) as *mut AVLTree;
        if new_tree.is_null() {
            return ptr::null_mut();
        }
        (*new_tree).root_node = ptr::null_mut();
        (*new_tree).compare_func = compare_func;
        (*new_tree).num_nodes = 0;
        new_tree
    }
}
fn avl_tree_free_subtree(tree: &mut AVLTree, node: *mut AVLTreeNode) {
    if node.is_null() {
        return;
    }
    unsafe {
        avl_tree_free_subtree(tree, (*node).children[AVL_TREE_NODE_LEFT as usize]);
        avl_tree_free_subtree(tree, (*node).children[AVL_TREE_NODE_RIGHT as usize]);
        libc::free(node as *mut libc::c_void);
    }
}
fn avl_tree_free(tree: *mut AVLTree) {
    unsafe {
        avl_tree_free_subtree(tree, (*tree).root_node);
        libc::free(tree as *mut libc::c_void);
    }
}
fn avl_tree_subtree_height(node: Option<&AVLTreeNode>) -> i32 {
    match node {
        None => 0,
        Some(n) => n.height,
    }
}
fn avl_tree_update_height(node: *mut AVLTreeNode) {
    let left_subtree = (*node).children[AVL_TREE_NODE_LEFT];
    let right_subtree = (*node).children[AVL_TREE_NODE_RIGHT];
    let left_height = avl_tree_subtree_height(left_subtree);
    let right_height = avl_tree_subtree_height(right_subtree);
    if left_height > right_height {
        (*node).height = left_height + 1;
    } else {
        (*node).height = right_height + 1;
    }
}
fn avl_tree_node_parent_side(node: &AVLTreeNode) -> AVLTreeNodeSide {
    unsafe {
        if (*node.parent).children[AVLTreeNodeSide::AVL_TREE_NODE_LEFT as usize] == node {
            AVLTreeNodeSide::AVL_TREE_NODE_LEFT
        } else {
            AVLTreeNodeSide::AVL_TREE_NODE_RIGHT
        }
    }
}
fn avl_tree_node_replace(tree: *mut AVLTree, node1: *mut AVLTreeNode, node2: *mut AVLTreeNode) {
    let mut side: usize;
    if !node2.is_null() {
        (*node2).parent = (*node1).parent;
    }
    if (*node1).parent.is_null() {
        (*tree).root_node = node2;
    } else {
        side = avl_tree_node_parent_side(node1);
        (*(*node1).parent).children[side] = node2;
        avl_tree_update_height((*node1).parent);
    }
}
fn avl_tree_rotate<'a>(
    tree: &'a mut AVLTree,
    node: &'a mut AVLTreeNode,
    direction: AVLTreeNodeSide,
) -> &'a mut AVLTreeNode {
    let new_root: &mut AVLTreeNode;
    new_root = node.children[1 - direction as usize].unwrap();
    avl_tree_node_replace(tree, node, new_root);
    node.children[1 - direction as usize] = new_root.children[direction as usize].take();
    new_root.children[direction as usize] = Some(Box::from_raw(node));
    node.parent = Some(new_root);
    if node.children[1 - direction as usize].is_some() {
        node.children[1 - direction as usize].unwrap().parent = Some(node);
    }
    avl_tree_update_height(new_root);
    avl_tree_update_height(node);
    return new_root;
}
fn avl_tree_node_balance<'a>(
    tree: &'a mut AVLTree,
    node: &'a mut AVLTreeNode,
) -> &'a mut AVLTreeNode {
    let left_subtree;
    let right_subtree;
    let mut child;
    let diff;
    unsafe {
        left_subtree = node.children[AVL_TREE_NODE_LEFT as usize];
        right_subtree = node.children[AVL_TREE_NODE_RIGHT as usize];
        diff = avl_tree_subtree_height(right_subtree) - avl_tree_subtree_height(left_subtree);
        if diff >= 2 {
            child = right_subtree;
            if avl_tree_subtree_height((*child).children[AVL_TREE_NODE_RIGHT as usize])
                < avl_tree_subtree_height((*child).children[AVL_TREE_NODE_LEFT as usize])
            {
                avl_tree_rotate(tree, child, AVL_TREE_NODE_RIGHT);
            }
            node = avl_tree_rotate(tree, node, AVL_TREE_NODE_LEFT);
        } else if diff <= -2 {
            child = node.children[AVL_TREE_NODE_LEFT as usize];
            if avl_tree_subtree_height((*child).children[AVL_TREE_NODE_LEFT as usize])
                < avl_tree_subtree_height((*child).children[AVL_TREE_NODE_RIGHT as usize])
            {
                avl_tree_rotate(tree, left_subtree, AVL_TREE_NODE_LEFT);
            }
            node = avl_tree_rotate(tree, node, AVL_TREE_NODE_RIGHT);
        }
        avl_tree_update_height(node);
        node
    }
}
fn avl_tree_balance_to_root(tree: &mut AVLTree, mut node: *mut AVLTreeNode) {
    let mut rover = node;
    while !rover.is_null() {
        rover = avl_tree_node_balance(tree, rover);
        unsafe {
            rover = (*rover).parent;
        }
    }
}
fn avl_tree_insert(tree: *mut AVLTree, key: AVLTreeKey, value: AVLTreeValue) -> *mut AVLTreeNode {
    let mut rover: *mut *mut AVLTreeNode = &mut (*tree).root_node;
    let mut previous_node: *mut AVLTreeNode = ptr::null_mut();
    while !(*rover).is_null() {
        previous_node = *rover;
        if ((*tree).compare_func)(key, (**rover).key) < 0 {
            rover = &mut ((**rover).children[AVLTreeNodeSide::AVL_TREE_NODE_LEFT as usize]);
        } else {
            rover = &mut ((**rover).children[AVLTreeNodeSide::AVL_TREE_NODE_RIGHT as usize]);
        }
    }
    let new_node: *mut AVLTreeNode = malloc(mem::size_of::<AVLTreeNode>()) as *mut AVLTreeNode;
    if new_node.is_null() {
        return ptr::null_mut();
    }
    (*new_node).children[AVLTreeNodeSide::AVL_TREE_NODE_LEFT as usize] = ptr::null_mut();
    (*new_node).children[AVLTreeNodeSide::AVL_TREE_NODE_RIGHT as usize] = ptr::null_mut();
    (*new_node).parent = previous_node;
    (*new_node).key = key;
    (*new_node).value = value;
    (*new_node).height = 1;
    *rover = new_node;
    avl_tree_balance_to_root(tree, previous_node);
    (*tree).num_nodes += 1;
    new_node
}
fn avl_tree_node_get_replacement(
    tree: &mut AVLTree,
    node: &mut Box<AVLTreeNode>,
) -> Option<Box<AVLTreeNode>> {
    let left_subtree = node.children[AVLTreeNodeSide::AVL_TREE_NODE_LEFT as usize].as_ref();
    let right_subtree = node.children[AVLTreeNodeSide::AVL_TREE_NODE_RIGHT as usize].as_ref();
    if left_subtree.is_none() && right_subtree.is_none() {
        return None;
    }
    let left_height = avl_tree_subtree_height(left_subtree);
    let right_height = avl_tree_subtree_height(right_subtree);
    let side = if left_height < right_height {
        AVLTreeNodeSide::AVL_TREE_NODE_RIGHT as usize
    } else {
        AVLTreeNodeSide::AVL_TREE_NODE_LEFT as usize
    };
    let mut result = node.children[side].as_mut().unwrap();
    while result.children[1 - side].is_some() {
        result = result.children[1 - side].as_mut().unwrap();
    }
    let child = result.children[side].take();
    let parent_ptr = result.parent.unwrap();
    unsafe {
        avl_tree_node_replace(tree, result, child);
        avl_tree_update_height(Some(&mut *parent_ptr));
    }
    Some(result)
}
fn avl_tree_remove_node(tree: &mut AVLTree, node: &mut AVLTreeNode) {
    let mut swap_node: *mut AVLTreeNode;
    let balance_startpoint: *mut AVLTreeNode;
    swap_node = avl_tree_node_get_replacement(tree, node);
    if swap_node.is_null() {
        avl_tree_node_replace(tree, node, std::ptr::null_mut());
        balance_startpoint = node.parent;
    } else {
        if unsafe { (*swap_node).parent } == node {
            balance_startpoint = swap_node;
        } else {
            balance_startpoint = unsafe { (*swap_node).parent };
        }
        for i in 0..2 {
            unsafe {
                (*swap_node).children[i] = node.children[i];
                if !(*swap_node).children[i].is_null() {
                    (*(*swap_node).children[i]).parent = swap_node;
                }
            }
        }
        unsafe {
            (*swap_node).height = node.height;
        }
        avl_tree_node_replace(tree, node, swap_node);
    }
    unsafe {
        libc::free(node as *mut _ as *mut libc::c_void);
    }
    tree.num_nodes -= 1;
    avl_tree_balance_to_root(tree, balance_startpoint);
}
fn avl_tree_remove(tree: &mut AVLTree, key: AVLTreeKey) -> i32 {
    let node: *mut AVLTreeNode;
    node = avl_tree_lookup_node(tree, key);
    if node.is_null() {
        return 0;
    }
    avl_tree_remove_node(tree, node);
    return 1;
}
fn avl_tree_lookup_node(tree: &AVLTree, key: AVLTreeKey) -> Option<&AVLTreeNode> {
    let mut node = tree.root_node;
    while let Some(current_node) = unsafe { node.as_ref() } {
        let diff = (tree.compare_func)(key, current_node.key);
        if diff == 0 {
            return Some(current_node);
        } else if diff < 0 {
            node = current_node.children[AVL_TREE_NODE_LEFT];
        } else {
            node = current_node.children[AVL_TREE_NODE_RIGHT];
        }
    }
    None
}
fn avl_tree_lookup(tree: *mut AVLTree, key: AVLTreeKey) -> AVLTreeValue {
    let node: *mut AVLTreeNode;
    node = avl_tree_lookup_node(tree, key);
    if node.is_null() {
        return std::ptr::null_mut();
    } else {
        unsafe {
            return (*node).value;
        }
    }
}
fn avl_tree_root_node(tree: &AVLTree) -> *mut AVLTreeNode {
    tree.root_node
}
fn avl_tree_node_key(node: &AVLTreeNode) -> AVLTreeKey {
    node.key
}
fn avl_tree_node_value(node: &AVLTreeNode) -> AVLTreeValue {
    node.value
}
fn avl_tree_node_child(node: &AVLTreeNode, side: AVLTreeNodeSide) -> Option<&AVLTreeNode> {
    match side {
        AVLTreeNodeSide::AVL_TREE_NODE_LEFT | AVLTreeNodeSide::AVL_TREE_NODE_RIGHT => {
            node.children[side as usize].as_ref()
        }
        _ => None,
    }
}
fn avl_tree_node_parent(node: &AVLTreeNode) -> Option<*mut AVLTreeNode> {
    node.parent
}
fn avl_tree_num_entries(tree: &AVLTree) -> u32 {
    tree.num_nodes
}
fn avl_tree_to_array_add_subtree(
    subtree: *mut AVLTreeNode,
    array: *mut AVLTreeValue,
    index: &mut i32,
) {
    if subtree.is_null() {
        return;
    }
    unsafe {
        avl_tree_to_array_add_subtree(
            (*subtree).children[AVL_TREE_NODE_LEFT as usize],
            array,
            index,
        );
        *array.add(*index as usize) = (*subtree).key;
        *index += 1;
        avl_tree_to_array_add_subtree(
            (*subtree).children[AVL_TREE_NODE_RIGHT as usize],
            array,
            index,
        );
    }
}
fn avl_tree_to_array(tree: &AVLTree) -> Option<Vec<AVLTreeValue>> {
    let mut array = Vec::with_capacity(tree.num_nodes as usize);
    if array.capacity() == 0 {
        return None;
    }
    let mut index = 0;
    avl_tree_to_array_add_subtree(tree.root_node, &mut array, &mut index);
    Some(array)
}

